#include <iostream>
#include <ostream>

// AVL 数的基本节点描述
struct Node
{
    int m_key;
    int m_height;
    Node* m_left;
    Node* m_right;

    // function
    Node():m_key(0),m_height(0),m_left(nullptr),m_right(nullptr){}
    Node(int key, Node* left=nullptr, Node* right=nullptr)
    {
        m_key = key;
        m_height = 0;
        m_left = left;
        m_right = right;
    }

};

class AVLInterface
{
public:
    virtual ~AVLInterface(){}
    virtual void insert(int key) = 0;
    virtual void remove(int key) = 0;
    virtual void output(std::ostream& os) const =0;
};

class AVL : public AVLInterface
{
public:
    AVL():m_root(nullptr), m_size(0){}
    ~AVL()
    {
        clear(m_root);
    }

    void insert(int key) override
    {
        insert(m_root, key);
    }

    void remove(int key) override
    {

    }

    void output(std::ostream &os) const override
    {
        std::cout<<"TODO"<<std::endl;
    }

private:
    void clear(Node* node)
    {
        if(node != nullptr){
            clear(node->m_left);
            delete node;
            clear(node->m_right);
        }
    }

    Node* leftLeftRotation(Node* k2)
    {
        Node* k1 = k2->m_left;
        k2->m_left = k1->m_right;
        k1->m_right = k2;

        updateHeight(k2);
        updateHeight(k1);
        return k1;
    }

    Node* rightRightRotation(Node* k2)
    {
        Node* k1 = k2->m_right;
        k2->m_right = k1->m_left;
        k1->m_left = k2;

        updateHeight(k2);
        updateHeight(k1);
        return k1;
    }

    Node* leftRightRotation(Node* k3)
    {
        k3->m_left = rightRightRotation(k3->m_left);
        return leftLeftRotation(k3);
    }

    Node* rightLeftRotation(Node* k3)
    {
        k3->m_right = leftLeftRotation(k3->m_right);
        return rightRightRotation(k3);
    }

    void updateHeight(Node* node)
    {
        int l = node->m_left == nullptr ? 0 : node->m_left->m_height;
        int r = node->m_right == nullptr ? 0: node->m_right->m_height;
        node->m_height = std::max(l,r) + 1;
    }

    Node* insert(Node* node, int key)
    {
        if(node == nullptr){
            node = new Node(key);
            return node;
        }else if (key < node->m_key) {
            node->m_left = insert(node->m_left, key);
            if(getHeight(node->m_left) - getHeight(node->m_right) ==2){
                if(key < node->m_left->m_key){
                    node = leftLeftRotation(node); // LL
                }else{
                    node = leftRightRotation(node); // LR
                }
            }
        }else if(key > node->m_key){
            node->m_right = insert(node->m_right, key);
            if(getHeight(node->m_right) - getHeight(node->m_left) ==2){
                if(key > node->m_right->m_key){
                    node = rightRightRotation(node);
                }else{
                    node = rightLeftRotation(node);
                }
            }
        }else{
            throw "The key exist.";
        }

        updateHeight(node);
        m_size++;

        return node;
    }

    int getHeight(Node* node)
    {
        if(node != nullptr) return node->m_height;
        else return 0;
    }

private:
    Node* m_root;
    int m_size;
};


int main(int argc, char *argv[])
{
    std::cout<<"TODO"<<std::endl;
    return 0;
}
